#define _CRT_SECURE_NO_WARNINGS
#include"test.h"

typedef struct ListNode
{
    int val;
    struct ListNode* next;
    struct ListNode* random;
    ListNode(const int& _val)
        :val(_val)
        , next(nullptr)
        , random(nullptr)
    {}

}Node;

class Solution {
public:
    Node* copyRandomList(Node* head)
    {
        map<Node*, Node*> m;
        Node* cur = head;
        while (cur != nullptr)
        {
            m[cur] = new Node(cur->val);
            cur = cur->next;
        }

        cur = head;
        Node* newhead = nullptr, * tail = nullptr;
        while (cur != nullptr)
        {
            if (newhead == nullptr)
            {
                tail = newhead = m[cur];
            }
            else
            {
                tail->next = m[cur];
                tail = tail->next;
            }
            cur = cur->next;
        }

        cur = head;
        while (cur != nullptr)
        {
            m[cur]->random = cur->random != nullptr ? m[cur->random] : nullptr;
            cur = cur->next;
        }
        return newhead;
    }
};